package com.gaogzhen.datastructure.graph.maintest;

import com.gaogzhen.datastructure.graph.directed.*;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;

import java.io.File;

/**
 * @author: Administrator
 * @createTime: 2023/03/19 19:45
 */
public class TestDirected {
    public static void main(String[] args) {
        // testDirectedDFS();
        // testDepthFirstDirectedPaths();
        // testBreadthFirstDirectedPaths();
        // testDirectedCycle();
        // testDepthFirstOrder();
        // testTopological();
        // testKosaraju();

        testTransitiveClosure();

    }

    /**
     * 测试传递闭包
     */
    public static void testTransitiveClosure() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyDG1.txt";
        In in = new In(path);
        Digraph G = new Digraph(in);

        TransitiveClosure tc = new TransitiveClosure(G);

        // print header
        StdOut.print("     ");
        for (int v = 0; v < G.V(); v++) {
            StdOut.printf("%3d", v);
        }
        StdOut.println();
        StdOut.println("--------------------------------------------");

        // print transitive closure
        for (int v = 0; v < G.V(); v++) {
            StdOut.printf("%3d: ", v);
            for (int w = 0; w < G.V(); w++) {
                if (tc.reachable(v, w)) {
                    StdOut.printf("  T");
                } else {
                    StdOut.printf("   ");
                }
            }
            StdOut.println();
        }
    }

    /**
     * 测试强连通分量
     */
    public static void testKosaraju() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyDG1.txt";
        In in = new In(path);
        Digraph digraph = new Digraph(in);
        KosarajuSharirSCC scc = new KosarajuSharirSCC(digraph);

        // number of connected components
        int m = scc.count();
        StdOut.println(m + " strong components");

        // compute list of vertices in each strong component
        Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
        for (int i = 0; i < m; i++) {
            components[i] = new Queue<Integer>();
        }
        for (int v = 0; v < digraph.V(); v++) {
            components[scc.id(v)].enqueue(v);
        }

        // print results
        for (int i = 0; i < m; i++) {
            for (int v : components[i]) {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }
    }

    /**
     * 测试拓扑排序
     */
    public static void testTopological() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyDGO.txt";
        In in = new In(path);
        Digraph digraph = new Digraph(in);
        Topological topological = new Topological(digraph);
        System.out.println(topological);

        System.out.println("是否可拓扑排序（是否是有向无环图）：" + topological.hasOrder());
        System.out.println("拓扑排序：" + topological.order());

        int v = 4;
        System.out.println("顶点：" + v + " 拓扑排列索引 " + topological.rank(v));
    }


    /**
     * 测试深度优先搜索顶点排序
     */
    public static void testDepthFirstOrder() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyDGO.txt";
        In in = new In(path);
        Digraph digraph = new Digraph(in);
        DepthFirstOrder depthFirstOrder = new DepthFirstOrder(digraph);
        System.out.println(depthFirstOrder);

        System.out.println("前序排列：" + depthFirstOrder.pre());
        System.out.println("后序排列：" + depthFirstOrder.post());
        System.out.println("逆后序排列：" + depthFirstOrder.reversePost());

        int v = 4;
        System.out.println("顶点：" + v + " 前序排列索引 " + depthFirstOrder.pre(v));
        System.out.println("顶点：" + v + " 后序排列索引 " + depthFirstOrder.post(v));
    }

    /**
     * 测试有向环
     */
    public static void testDirectedCycle() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyDAG.txt";
        In in = new In(path);
        Digraph digraph = new Digraph(in);
        DirectedCycle cycle = new DirectedCycle(digraph);
        System.out.println(cycle);
        int v = 0;
        System.out.println(cycle.hasCycle());
        System.out.println(cycle.cycle());
    }

    /**
     * 测试有向图最短路径
     */
    public static void testBreadthFirstDirectedPaths() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyDG.txt";
        In in = new In(path);
        Digraph digraph = new Digraph(in);
        // List<Integer> integers = Arrays.asList(0, 2);
        BreadthFirstDirectedPaths paths = new BreadthFirstDirectedPaths(digraph, 0);

        int v = 2;
        System.out.println(paths.distTo(v));
        System.out.println(paths.pathTo(v));
    }

    /**
     * 测试有向图单点路径
     */
    public static void testDepthFirstDirectedPaths() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyDG.txt";
        In in = new In(path);
        Digraph digraph = new Digraph(in);
        int s = 0;
        DepthFirstDirectedPaths directedPaths = new DepthFirstDirectedPaths(digraph, s);

        int v = 2;
        System.out.println(directedPaths.hasPathTo(v));
        System.out.println(directedPaths.pathTo(v));
    }

    /**
     * 有向图深度优先搜索
     */
    public static void testDirectedDFS() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyDG.txt";
        In in = new In(path);
        Digraph graph = new Digraph(in);
        int s = 0;
        DirectedDFS directedDFS = new DirectedDFS(graph, s);

        int t = 5;
        System.out.println(directedDFS.marked(t));
        System.out.println(directedDFS.count());
    }
}
